#include<iostream>
using namespace std;
const int max_n = 1e8 + 10;
void get_prime(int n)
{
    int visited[max_n], prime[max_n];
    int m = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 2; i <= n; i++)
    {
        if (!visited[i]) prime[m++] = i;
        for (int j = 0; j < m && prime[j] * i <= n; j++)
        {
            visited[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}